package algo.A01_位运算;

import org.junit.Test;
import util.ArrayUtil;

import java.util.Random;

/**
 * 1-1000这1000个数放在含有1001个元素的数组中，
 * 只有唯一的一个元素重复，其他均只出现一次。
 * 每个数组元素只能访问一次，设计一个算法，将它找出来；
 * 不用辅助存储空间，设计一个算法实现
 */
public class T01_唯一成对的数 {
    /**
     * 解法：此处可以使用异或，同0异1的特性
     * 将1-1000异或起来，结果一定为0.再与1001个元素的数组异或
     * 0与任意元素异或运算，其结果为元素本身，这样就得到了重复的数
     *
     * @param args
     */
    @Test
    public static void main(String[] args) {
        //模拟一个只有一个重复元素的数组
        int LEN = 1001;
        int[] array = new int[LEN];
        Random r = new Random();
        //随机生成一个要与最后一个数调换的下标
        int index = r.nextInt(LEN);
        for (int i = 0; i < array.length - 1; i++) {
            array[i] = i + 1;//为每个元素赋值1,2,3...
        }
        //最后一个元素是1-1000随机生成
        array[LEN - 1] = r.nextInt(LEN - 1) + 1;
        ArrayUtil.swap(array, index, LEN - 1);
        ArrayUtil.print(array);

        //开始解题
        solution1(array);//不开辟新空间
        solution2(array);//开辟新空间
    }

    /**
     * 不开辟新空间，使用异或运算解题
     *
     * @param array
     */
    private static void solution1(int[] array) {
        int result = 0;
        //result = 0^1^2^3^4^...^1000
        for (int i = 1; i < array.length; i++) {
            result = result ^ i;
        }
        //result与每一个元素异或，如果有两个元素相同就会抵消为0
        //如果不同则为原值，这样有1000个元素都能被抵消为0，只剩下那个不同的
        for (int i = 0; i < array.length; i++) {
            result = result ^ array[i];
        }
        System.out.println("result = " + result);
    }

    /**
     * 开辟新空间.新空间的每个下标统计原数组每个元素的出现次数
     * 例如元素39出现一次，则a[39]++
     *
     * @param array
     */
    private static void solution2(int[] array) {
        int result;
        int[] helper = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            helper[array[i]]++;
            if (helper[array[i]] > 1) {
                result = array[i];
                System.out.println("result = " + result);
            }
        }

    }
}
